package codetop.microsoft.T146;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 18362
 * @Create: 2022-08-13 8:55:37 星期六
 */
public class Solution {

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

    static class LRUCache {

        private int capacity;
        private DoubleLinkedHashList list = new DoubleLinkedHashList();

        static class Node {
            int key;
            int value;
            Node next;
            Node prev;
            Node() {}
            Node(int k, int v) {
                key = k;
                value = v;
            }
        }

        static class DoubleLinkedHashList {
            Node head;
            Node tail;
            private Map<Integer, Node> map = new HashMap<>();

            DoubleLinkedHashList() {
                head = new Node();
                tail = new Node();
                head.next = tail;
                tail.prev = head;
            }

            int getSize() {
                return map.size();
            }

            boolean containsKey(int key) {
                return map.containsKey(key);
            }

            int get(int key) {
                return map.get(key).value;
            }

            void removeFromTail() {
                Node node = tail.prev;
                removeFromList(node);
                map.remove(node.key);
            }

            void refresh(int key, int value) {
                Node node = map.get(key);
                node.value = value;
                removeFromList(node);
                addToHead(node);
            }

            void put(int key, int value) {
                Node node = new Node(key, value);
                map.put(key, node);
                addToHead(node);
            }

            private void addToHead(Node node) {
                head.next.prev = node;
                node.next = head.next;
                head.next = node;
                node.prev = head;
            }

            private void removeFromList(Node node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
        }

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if (list.containsKey(key)) {
                int value = list.get(key);
                list.refresh(key, value);
                return value;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (list.containsKey(key)) {
                list.refresh(key, value);
            } else {
                if (list.getSize() == capacity) {
                    list.removeFromTail();
                }
                list.put(key, value);
            }
        }
    }
}
